3263. Как склеить число?

 

В вашем распоряжении есть все натуральные числа с диапазона от 10 до 99 включительно. Вычислите количество способов выбрать из них точно k разных чисел (порядок выбора имеет значение) так, что после "склеивания" их в одну большую строку, полученное число будет  делится на x.

 

Вход. В первой строке содержится количество тестов t (1 ≤ t ≤ 100). Каждый тест задается в отдельной строке и содержит два числа: k (1 ≤ k ≤ 5) и x (1 ≤ x ≤ 100), разделённых пробелом.

 

Выход. Для каждого теста выведите в отдельной строке ответ в соответствии с форматом, указанным в примере.

 

Пример входа

Пример выхода

3

2 17

1 5

3 21

Case #1: 471

Case #2: 18

Case #3: 33726

 

 

РЕШЕНИЕ

динамическое программирование - маски подмножеств

 

Анализ алгоритма

Рассмотрим большую строку, полученную в результате склейки k чисел. Будем говорить, что она имеет k позиций, на каждой из которых может находиться любое из чисел от 10 до 99. Процесс склейки будем проводить методом полного перебора, стараясь поставить в каждую позицию каждое из возможных чисел (от 10 до 99). На текущий момент не обязательно все k позиций могут быть заполнены. Например, если k = 5, а вставлены только два числа 10 и 11 соответственно на нулевое и второе место (нулевое место – крайнее правое), то такую строку будем кодировать в виде **11*10. Звездочкой будем обозначать пустое место.

Маской большой строки будем называть такую последовательность из нулей и единиц, в которой единицы стоят только на тех местах, в которых уже вставлены числа. Например, строка **11*10 соответствует маске 001012 = 5.

Пусть dp[i][mask][ost] содержит количество больших чисел, которое можно получить склейкой чисел из диапазона от 10 до i (10 ≤ i ≤ 99) включительно так, что их остаток от деления на x равен ost (0 ≤ ost < x). При этом склейка больших чисел должна соответствовать маске mask. То есть если mask содержит в двоичном представлении в точности из k единиц, то большие числа должны быть склеены ровно из k чисел, каждое из которых находится в пределах от 10 до 99.

Рассмотрим некоторое длинное число А, склейка которого соответствует маске mask, в котором используются только числа от 10 до i – 1, а остаток от деления его на x равен ost. Тогда это число учитывается при вычислении dp[i – 1][mask][ost]. Очевидно, что все числа из dp[i – 1][mask][ost] должны учитываться в dp[i][mask][ost]. Пусть мы на данный момент стараемся вклеить в А число i. Очевидно, что его можно вклеить только в ту позицию, в которой в маске mask находится ноль (если таких позиций не существует, то произвести вклейку невозможно). Если число i можно вклеить в k-ую позицию числа А, то после вклейки полученное длинное число при делении на x будет давать остаток (ost + i * 100k) % x, а маска полученного числа составит mask or (1 shl k). Таким образом все числа, учтенные в dp[i – 1][mask][ost], следует прибавить к dp[i][mask | (1 << k)][ (ost + i * 100k) % x]. Причем следует перебрать все возможные для вклейки позиции k.

 

Пример

Пусть k = 4, x = 3.

dp[11][3][0] = 2, наборы **1011, **1110.

dp[11][5][0] = 2, наборы *10*11, *11*10.

dp[11][9][0] = 2, наборы 10**11, 11**10.

dp[11][12][0] = 2, наборы 1011**, 1110**.

 

dp[12][12][0] = 2, наборы 1011**, 1110** (остаток от деления на 3 равен 0).

dp[12][12][1] = 2, наборы 1012**, 1210** (остаток от деления на 3 равен 1).

dp[12][12][2] = 2, наборы 1112**, 1211** (остаток от деления на 3 равен 2).

 

dp[12][14][0] = 6, наборы 101112*, 101211*, 111012*, 111210*, 121011*, 121110*.

 

Реализация алгоритма

Степени сотни храним в массиве pow100: pow100[i] = 100i. Объявим массив dp. Поскольку таблица dp[i + 1][][] пересчитывается через таблицу dp[i][][], объявим в dp размерность первого аргумента равную 2. Таким образом dp[1][][] пересчитываем через dp[0][][], а потом dp[0][][] пересчитываем через dp[1][][].

 

long long pow100[5] = {1, 100, 10000, 1000000, 100000000};

long long dp[2][1 << 5][101];

 

Читаем входные данные.

 

scanf("%d", &t);

for (test = 1; test <= t; test++)

{

  memset(dp, 0, sizeof(dp));

  scanf("%d %d", &k, &x);

 

  dp[1][0][0] = 1;

 

Перебираем числа от 10 до 99, которые будем вклеивать.

 

  for (i = 10; i < 100; i++)

  {

 

Перебираем остатки от деления на х (от 0 до x – 1).

 

    for (ost = 0; ost < x; ost++)

    {

 

Перебираем маски в убывающем порядке от 2k – 1 до 0.

 

      for (mask = (1 << k) - 1; mask >= 0; mask--)

      if (dp[(i + 1)% 2][mask][ost])

      {

        dp[i % 2][mask][ost] += dp[(i + 1)% 2][mask][ost];

 

Перебираем позиции g в маске mask. В те позиции, в которых в маске стоят нули, вклеиваем число i.

 

        for (int g = 0; g < k; g++)

          if (!(mask & (1 << g)))

            dp[i % 2][mask | (1 << g)][(ost + i * pow100[g]) % x] +=

            dp[(i + 1)% 2][mask][ost];

 

Очищаем обработанную ячейку.

 

        dp[(i + 1)% 2][mask][ost] = 0;

      }

    }

  }

 

Выводим ответ.

 

  printf("Case #%d: %I64d\n", test, dp[(i + 1)% 2][(1 << k) - 1][0]);

}